class Solution1 {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = g[0] = nums[0];
        int sum = nums[0];
        for(int i = 1; i<n; i++) {
            sum += nums[i];
            f[i] = Math.max(f[i-1] + nums[i], nums[i]);
            g[i] = Math.min(g[i-1] + nums[i], nums[i]);
        }
        int max = f[0], min = g[0];
        for(int i = 1; i<n; i++) {
            max = Math.max(max,f[i]);
            min = Math.min(min,g[i]);
        }
        System.out.println(max + " " + min + " " + sum);
        int ret = Math.max(max, sum - min);
        if(sum - min == 0) ret = max;
        return ret;
    }
}


class Solution2 {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0];
        for(int i = 1; i<n; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[n-1],g[n-1]);
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1]; //最大乘积
        int[] g = new int[n+1]; //最小乘积
        f[0] = 1; g[0] = 1;
        for(int i = 1; i<=n; i++) {
            f[i] = Math.max(Math.max(nums[i-1], f[i-1]*nums[i-1]), g[i-1]*nums[i-1]);
            g[i] = Math.min(Math.min(nums[i-1], f[i-1]*nums[i-1]), g[i-1]*nums[i-1]);
        }

        int ret = f[1];
        for(int i = 1; i<=n; i++) {
            ret = Math.max(ret,f[i]);
        }

        return ret;
    }
}

public class Test {

}
